package ljl.alg.jianzhioffer.round3.medium;

public class _47_maxValue {

    class normal {
        public int maxValue(int[][] grid) {
            int m = grid.length, n = grid[0].length;
            int[][] dp = new int[m + 1][n + 1];
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    dp[i][j] = grid[i - 1][j - 1] + Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
            return dp[m][n];
        }
    }

    class zip {
        public int maxValue(int[][] grid) {
            int m = grid.length, n = grid[0].length;
            int[] dp = new int[n];
            dp[0] = grid[0][0];
            for (int i = 1; i < n; i++) {
                dp[i] = grid[0][i] + dp[i - 1];
            }
            for (int i = 1; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    dp[j] = grid[i][j] + (j == 0 ? dp[j] : Math.max(dp[j], dp[j - 1]));
                }
            }
            return dp[n - 1];
        }
    }
}
